/*Copyright (c) Microsoft Open Technologies, Inc.  All rights reserved.
Microsoft Open Technologies would like to thank its contributors, a list
of whom are at https://interview.codeplex.com/team/views.

Licensed under the Apache License, Version 2.0 (the "License"); you
may not use this file except in compliance with the License. You may
obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
implied. See the License for the specific language governing permissions
and limitations under the License.

Author: everyday (weijie.he@live.com)
*/

#include "list.h"
#include <iostream>

using namespace std;

// Problem: sort a singly link list by Quick Sort
node *partition(list &l, node *&begin, node *end = nullptr) {
    // if end is the next node, that means it's only one node to sort
    if (begin == nullptr || end == begin->next) {
        return nullptr;
    }

    list small_list, big_list;
    node *current = l.root;
    node *pivot = begin;
    node **pbegin;          // points to the address of begin
    node **s_current = &small_list.root, **b_current = &big_list.root;

    // move previous nodes before 'begin' to small list
    while (current != begin) {
        *s_current = current;
        s_current = &(*s_current)->next;
        current = current->next;
    }

    // pbegin presents the location(address) of begin item, e.g. if (a->next == begin) then pbegin = &a->next;
    pbegin = s_current;

    while (begin != end) {
        if (begin->data < pivot->data) {
            *s_current = begin;
            s_current = &(*s_current)->next;
        }
        else {
            *b_current = begin;
            b_current = &(*b_current)->next;
        }

        begin = begin->next;
    }

    // pass begin back to quick_sort for next sort action
    begin = *pbegin;

    *b_current= end;
    *s_current = big_list.root;
    l = small_list;
    l.print();

    // current pivot would be the end node for smaller set sorting
    return big_list.root;
}

void quick_sort(list &l, node *begin, node *end = nullptr) {
    if (begin == end) {
        return;
    }
    // mid represents the pivot node which is the next node of the end of the small list
    node *mid = partition(l, begin, end);

    if (mid != nullptr){
        quick_sort(l, begin, mid);
    }

    if (mid != nullptr &&
        mid->next != nullptr) {        
        quick_sort(l, mid->next, end);
    }
}

int main() {
    list l;
    l.build_list("26 25 9 33 20 6 10");
    l.print();

    quick_sort(l, l.root);

    l.print();

    return 0;
}